public class Solution {
    //JZ53 数字在升序数组中出现的次数
    //计数器
    private int count = 0;
    public int GetNumberOfK(int [] array , int k) {
        //由于时间复杂度为O(logn)，所以要利用二分查找先找到这个数
        int len = array.length;
        int left = 0;
        int right = len - 1;
        int keyIndex = dichotomize(array, left, right, k);
        if(count == -1){
            return 0;
        }
        //因为有序，所以分别向两边扩展找相同的元素，找到了，计数就加1
        //左扩展
        left = keyIndex - 1;
        while(left >= 0 && array[left] == k){
            count++;
            left--;
        }
        //右扩展
        right = keyIndex + 1;
        while(right < len && array[right] == k){
            count++;
            right++;
        }
        return count;
    }
    //二分查找
    private int dichotomize(int[] array, int left, int right, int k){
        while(left <= right){
            int mid = (left + right) / 2;
            if(k < array[mid]){
                right = mid - 1;
            }else if(array[mid] < k){
                left = mid + 1;
            }else{
                count++;
                return mid;
            }
        }
        return -1;
    }
    //JZ4 二维数组中的查找
    public boolean Find(int target, int [][] array) {
        //每一行进行二分查找
        for(int i = 0; i < array.length; i++){
            boolean flay = binarySearch(target, array[i]);
            if(flay){
                return true;
            }
        }
        return false;
    }
    public boolean binarySearch(int target, int[] array){
        int left = 0;
        int right = array.length - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(target < array[mid]){
                right = mid - 1;
            }else if(target > array[mid]){
                left = mid + 1;
            }else{
                return true;
            }
        }
        return false;
    }
    //JZ11 旋转数组的最小数字
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //若中间值大于最右边，说明目标在中间值右边
            if(array[mid] > array[right]){
                left = mid + 1;
            }
            //此时不确定，比如 1 1 1 0 1，所以继续缩小范围
            else if(array[mid] == array[right]){
                right--;
            }
            //不在右边就在左边
            else{
                right = mid;
            }
        }
        return array[left];
    }
}
